import java.util.Arrays;

public class Kmp {
    public static void main(String[] args) {
        String str1 = "BBC ABCDAB ABCDABCDABDE";
        String str2 = "ABCDABD";
        String str="ABCDABD";
        int[] next=new int[str1.length()];
        System.out.println(Arrays.toString(kmp(str)));
        System.out.println(kmp01(str1,str2,next));
    }



    public static int kmp01(String str1,String str2,int[] next){
        for (int i = 0,j=0; i < str1.length(); i++) {
            while (j>0&&str1.charAt(i)!=str2.charAt(j)){
                j=next[j-1];
            }
            if (str1.charAt(i)==str2.charAt(j)){
                j++;
            }
            next[i]=j;
            if (j==str2.length()){
                return i-j+1;
            }
        }
        return -1;

    }


    public static int[] kmp(String dest){
        int[] next=new int[dest.length()];
        next[0]=0;
        for (int i = 1,j=0; i < dest.length(); i++) {
            while (j>0&&dest.charAt(i)!=dest.charAt(j)){
                j=next[j-1];
            }
            if (dest.charAt(i)==dest.charAt(j)){
                j++;
            }
            next[i]=j;
        }
            return next;
    }


}
